1. Field of the Invention
The present invention relates generally to group keying systems and more particularly to a group key distribution mechanism.
2. Discussion of the Related Art
Secure group communication is gaining in importance, with both military and commercial applications in need of development. In a secure group communication, a trusted key server communicates with a group of N users over a multicast or broadcast communications channel. The trusted key server also communicates with the group of N users through N respective unicast communications channels that enable communications with individual users.
A unicast communications channel can be embodied in various forms. In one example, the unicast communications channel is implemented online protected by a shared secret. In another example, the unicast communications channel is implemented offline through the physical delivery of a floppy disk. A multicast or broadcast channel can also be embodied in various forms, such as a wireless network, the public Internet, a cable network, a satellite network, a hybrid network, or the like.
In a secure group communication, each of the N users is a member of a group that uses a group key to encode and decode group communications. The group key is known to each user and to the key server.
In the normal course, users will frequently join and leave the group. It is therefore important to ensure that only the set of current users has access to a currently valid and secure group key. Specifically, the current group key should be secure against collaborative attacks from past and future users.
Many conventional algorithms are able to use the broadcast channel to communicate information necessary to evict a user or users from the group or to add a user or users to the group. Some conventional algorithms have been adopted that reduce the bandwidth used on the broadcast channel to perform key operations by using a hierarchy of keys assigned to nodes in a tree. These keys are used to communicate update information in an efficient manner when a new group key is needed due to membership changes.
FIG. 1 shows an example of a hierarchical set of keys used to limit the bandwidth required for updating a set of 32 users. Each node in hierarchical tree 100 is associated with a key. The nodes in the bottom row of hierarchical tree 100 are referred to as leaf nodes. The leaf nodes are associated with keys that are unique to individual users U0–U31. Specifically, user U0 is associated uniquely with the leftmost node in the bottom row, i.e., the leftmost leaf node; user U1 is associated with the next leaf node; and so on.
Higher nodes in the hierarchy are associated with sets of users, and are referred to as interior nodes. Each interior node is associated with a key known to one or more users that descend from that node. For example, the top most key, key A (the group key), is known by users U0–U31 that descend from it, key B is associated with users U0–U15 that descend from it, and key D is associated with users U0–U7 that descend from it.
In hierarchical tree 100, each user U0–U31 knows the keys corresponding to the path from its leaf node up to the root node A on top. For example, user U2 knows its unique key, and also knows its parent node key K, its grandparent node key H, and higher level node keys D, B, and A. Each user therefore knows one key per level of hierarchical tree 100 on the way to the root node A.
In general, tree hierarchies do not have to be symmetric or binary as illustrated in FIG. 1. Trees can have branching other than binary branching such that each node in the tree can have one or more nodes directly under it. For example, a hierarchical tree can be defined such that an interior node could have four nodes directly under it.
Additionally, hierarchical trees do not have to have a uniform depth. For example, some users could be at leaf nodes on the sixth level, as in hierarchical tree 100, while other users could be at leaf nodes at the eighth, ninth, or tenth levels at other places in the tree.
If a user is evicted, all of the keys the evicted user knows need to be replaced with new keys. This process ensures that only authorized users have access to the secure group communication. For example, in hierarchical tree 100, user U0 is illustrated as being evicted. Therefore, the circled keys, namely keys A, B, D, H, and J, are compromised and need to be replaced. The reason the key uniquely known to user U0 is not circled is that no other user knows that key. Therefore, key U0 will not be used again. If a new user is later added to the group and assigned to user U0's leaf node, that new user will be assigned a new key uniquely associated with it that cannot be derived from the old user U0's unique key.
Each non-evicted user that knows a key that is compromised through an eviction must learn the value of the replacement key. One conventional method for communicating new values for compromised keys from a key server to a non-evicted user is the logical key hierarchy (LKH) method, described in section 4.2 of Wallner et al., “Multicast Security: a Taxonomy and Some Efficient Constructions,” Sep. 15, 1998, which is hereby incorporated by reference in its entirety. In the LKH method, all compromised keys are generated at the key server, i.e., the key server determines replacement values for them. These values are then communicated in an efficient way to the remaining non-evicted users.
In FIG. 2, the LKH method is illustrated for hierarchical tree 100. Encrypted messages containing replacement keys are sent out, as indicated by the arrows in FIG. 2. The encrypted messages are depicted by arrows pointing at the nodes by whose keys they are encrypted. For example, the message encrypted with key B is depicted by an arrow pointing from node A towards node B. The encrypted message is labeled ‘EB’ to indicate that it is encrypted with key B.
As mentioned previously, the circled keys A, B, D, H, and J need to be replaced. In the LKH method, replacement key distribution begins at the bottom of the tree and progresses upward. In this framework, the first key to be replaced is key J. Key J is known to non-evicted user U1, and so its new value should be given to user U1. The key unique to user U1 is regarded as a leaf node key. Therefore, user U1 receives the new key J through a message EU1 that is encrypted with U1's leaf node key.
The next key to be replaced is key H. Users U1–U3 should be given the new value of key H. Here, key K is used to communicate the new value of key H to users U2 and U3, while the new key J is used to communicate the new value of key H to user U1. Specifically, user U1 receives the new value of key H through a message EJ that is encrypted with the new key J, while users U2 and U3 receive the new value of key H through a message EK that is encrypted with key K. Encryption under the new key J prevents evicted users from decrypting message EJ and obtaining the new value of key H.
Users U1–U7 are also given the new value of key D. Users U1–3 receive the new key D through a message EH that is encrypted with the new key H, while users U4–U7 receive the new key D through a message EI that is encrypted with key I. Next, users U1–U15 receive the new value of key B. Users U1–U7 get key B by decrypting message ED, while users U8–U15 get key B by decrypting message EE. Finally, users U1–U15 get the new group key A by decrypting message EB, while users U16–U31 get the new group key A by decrypting message EC.
As thus described, the LKH method enables secure distribution of new interior node keys upon eviction of one or more users. Two additional key distribution methods have been proposed to reduce the number of encrypted messages that are needed to a tree update after a single user is evicted. These methods are the one-way function chain (OFC) and one-way function tree (OFT) methods. The OFC method is described in section 4.2 of Canetti et al., “Multicast Security: A Taxonomy and Some Efficient Considerations,” Proceedings of IEEE Infocom'99, March 1999, which is hereby incorporated by reference in its entirety. The OFT method is described in McGrew et al., “Key Establishment in Large Dynamic Groups Using One-Way Function Trees,” May 20, 1998, which is hereby incorporated by reference in its entirety.
In the OFC method, the messages shown with the dotted arrows in FIG. 2 are eliminated, while the messages with the solid arrows are retained. In the OFT method, the messages are sent to the siblings instead of the children, such that there would be a message from B encrypted to C, from D encrypted to E, from H encrypted to I, from J encrypted to K and from a new U0 to U1. Both OFC and OFT require less messaging because replacement keys are a function of one (in OFC) or both (in OFT) children keys.
It should be noted that it is possible for multiple users to be evicted from the group simultaneously. This could happen, for example, if multiple users are compromised over a period of time and the key server evicts them all at the end of the period of time (e.g., end of a subscription period). This aggregates the eviction process for reasons of efficiency.
For example, suppose that users U0 and U13 are evicted simultaneously. As can be seen in FIG. 1, the keys known by evicted user U0 that are known by other users are keys A, B, D, H, and J. The keys known by evicted user U13 that are known by other users are keys A, B, E, N, and O. Therefore, keys A, B, D, E, H, J, N, and O should be replaced. This simultaneous double-eviction prevents keys A and B from being replaced twice.
In a large tree encompassing thousands or millions of users, many compromised users could accrue during a time interval. When they are simultaneously evicted after the time interval, there may exist a large number of keys that need to be replaced, particularly toward the bottom of the tree. For example, assume a worst case scenario in which every other user (i.e., users U0, U2, U4, U6, . . . ) is evicted. In a symmetric binary tree having 32 leaf nodes, 16 separate encrypted messages would be required to inform the non-evicted users (i.e., users U1, U3, U5, U7, . . . ) of the replacement keys for the first level of interior nodes above the leaf nodes. Additional encrypted messages would also be required to replace the rest of the compromised keys at higher levels of the tree. This communication cost becomes excessive when the tree encompasses millions of users. What is needed therefore is an efficient group key distribution mechanism.